, c A B H c d ∑ ∫ Ô 5 û C < C • i ∫ 5 ≤ ¿ Õ è t u ¡ 6 I [ • ‚ € ¥ U ` s ∑ + ¢ Â ß ê • 5 « î 5 !ï "# 5 "¬ $g %8 F &˘ '1 '\ 5 ( (8 5 (Ç ) ) )9 > )} > )Ô > ** *+ *ò + + +} +Ë , ,] ,˚ ,ê 5 72 7ˆ 5 7ÿ < 8 8å 8ø 8ù :≠ ;÷ = 7 = = S =A S =˝ S =Ä S =ÿ > V > > >T
QuickDraw GX ConicLibrary.c in Detail: Description and Derivations
By Cary Clark
cary@artemis.com
Apple Emeritus
This Technote discusses ConicLibrary.c from the QuickDraw GX Libraries.
This Note is intended for Macintosh QuickDraw GX developers who want to approximate ellipses and hyperbolas with paths. These, with parabolas (gxCurves), form the familty of curves called conics.
About the GX Libraries
For better or worse, the development of QuickDraw GX took seven years from conception to initial release. During that time, there were many requests for feature enhancements and interface improvements that, if implemented, might have taken seven more years to complete. As it turns out, some of these enhancements could readily be built on existing services, but there was no time to test or document these services with the rigor required to make them fully part of the released system.
The GX Libraries fill this gap by providing services built on top of the rest . of QuickDraw GX in source form. This Technote and others document these services. Since GX libraries are provided as source, it is reasonable for developers to modify them to meet their specific needs. Care was taken for the libraries not to depend on the implementation details of QuickDraw GX so that future versions should not invalidate them, in original or modified form.
The libraries are likely to evolve to take advantage of improved algorithms, as well as new Macintosh or QuickDraw GX services. If you modify one for your applicationÕs specific ne Ëeds, itÕs worth occasionally reviewing the GX library provided by Apple to stay synchronized with any improvements.
What is in ConicLibrary.c?
The GX Library, ConicLibrary.c, generates conics, a family of curves that include circles, ellipses, parabolas and hyperbolas. It was written by Michael Reed (the guy behind GX Fonts and TrueType) from a math paper derived by Robert Johnson, the GX resident mathematics professor.
Using ConicLibrary.c
A Conic is a gxCurve, Almost
ConicLibrary.c uses the conic struct:
struct conic {
gxPoint a;
gxPoint b;
gxPoint c;
Fixed lambda;
};
This is nearly the same as the gxCurve struct; it differs only by the additional lambda parameter. (Mike was a math major, too.) The lamba specifies the curvature. If the curvature is equal to one, the conic is a parabola, and is identical to a gxCurve (also known as a quadratic B⁄zier) with the same three points, as illustrated in Figure 1.
In Figure 1, as lambda decreases, the curv Óe approaches the line from point a to point b. All of these curves are elliptical arcs. When lambda hits zero, the curve has become a line from point a to point c.
As lambda increases, the curve approaches point b. These curves are hyperbolas. Once lambda gets big enough, the curve approximates two line segments: one from point a to point b, and another from point b to point c.
Figure 1 - A Quadratic Rational Spline with Vertices (a,b,c)
One reasonable use of the ConicLibrary provides a graphics application with a means to change the amount of curvature defined by a quadratic B⁄zier, a segment of a gxPath. To increase the curvature, simply increase lambda.
Conic Functions
Before we get into what the various values for lambda do, letÕs take a look at the conic library functions.
NewConic
gxShape NewConic(const conic *curve);
NewConic creates a path which approximates the conic. It subdivides the original conic into a pair of conics, recursively, unt ≈il the gxCurve described by the smaller conic has a sufficiently small error. The error is set by the default pathÕs shape error, which is initially 1.0. You can set it to a larger or smaller error with:
DrawConic creates the path shape, draws it with the specified fill, and throws it away. The fill can be any gxShapeFill value that works with a path; gxOpenFrameFill is the most common choice.
This replaces the geometry in an existing shape with a path that approximates the conic.
It is not necessary to understand lambda in mathematical terms. Its usefulness for ConicLibrary.c can be summarized by the following: increasing lambda increases curvature, while decreasing lambda decreases the curvature.
ù
Note:
These functions are orthogonal to other GX Graphics primitives, such as points, lines, polygons and paths, and other libraries, such as cubics, arcs, ovals and rounded rectangles. You can rely on functions of the form NewX, SetX and DrawX for any geometry supported by QuickDraw GX.
The Theory behind ConicLibrary.c
In the discussion that follows, several liberties are taken. Since the reader is assumed to be a programmer, not a mathematician, most of the equations that follow are in C++ rather than in mathematical notation. The non-existent structs fPoint, fCurve and fConic are introduced, to make the code easier to read. They are defined as:
struct fPoint {
float x;
float y;
};
struct fCurve {
fPoint first;
fPoint control;
fPoint last;
} Ê;
struct fConic {
fPoint a;
fPoint b;
fPoint c;
float lambda;
};
Note:
My apologies to the mathematicians of the world for bastardizing concepts, to the C programmers of the world for using C++, and to the GX Engineers for using not using Fixed.
There are (at least) two ways of describing conics. First, the ones that use x and y in equations you vaguely remember from high school:
circle: x2 + y2 = 0
parabola: x = y2
hyperbola: x2 - y2 = 1
ellipse: x2/a + y2/b = 0
WeÕre going to mostly ignore these, except to note that they can all be generalized by:
conic: ax2 + bx + cy2 + dy + exy + f = 0
This looks suspicously like the equation describing a parabola (with the right values of a, b, c, d, e and f) ‹ a gxCurve; and it is. LetÕs see how.
Describing a Curve
The general conic equation asserts that any equation of order 2 in x and y describes a conic. A conic, in turn, is described as a plane section of a pair of cones, stacked point to point. Slicing these cones reveals the familiar circles, ellipses, parabolas and hyperbolas.
ThereÕs another way to describe a parabola: as a parametric equation. A parametric equation (at least as they are going to be described here) describes x and y in terms of two equations as a third parameter, t, varies from zero to one. The equation for a second order parametric equation is:
x = at2 + bt + c
y = dt2 + et + f
ItÕs easy to see how this describes at least a non-rotated parabola; setting a or d to zero allows specifying an xy equation where either x or y is squared. More importantly for computers, itÕs easy to turn this equation into a forward differencing algorithm that allows approximating the curve as a series of lines with computations no more complicated than adds and shifts ..
If the curve described by these equations is limited by t starting at zero and ending at one, then the curve begins at (c, f) and ends at (a + b + c, d + e + f). Plugging in 0.5 for t yields the curveÕs midpoint; i.e., x = a/4 + b/2 + c. It is convenient to be able to define a curve by where it starts and ends; all thatÕs missing is some additional information that describes how it curves. A gxCurve describes a parabolic segment in terms of three control points, named first, control and last. We can describe those points in terms of their parametric parameters:
first = c
control = b/2 + c
last = a + b + c
The control point is formed by intersecting the tangent lines at the start and end of the curve. We can express the mid point in terms of first, control and last by:
mid = a/4 + b/2 + c = c/4 + b /4 + c/2+ (a + b + c)/4 = first/4 +control/2 + last/4
Solving for a, b and c results in:
a = first - 2 * control + last
b = control * 2 - first * 2
c = first
By substituting the above equations, we can specify a pair of parametric equations that describe a curve, given three points: (C++ code begins here:)
x = cu.first.x * ( 1 - t) * D (1 - t) + 2 * cu.control.x * t * (1 - t) + cu.last.x * t * t;
y = cu.first.y * ( 1 - t) * (1 - t) + 2 * cu.control.y * t * (1 - t) + cu.last.y * t * t;
}
Thus, the mid point of the curve is computed to be:
if ( t == 0.5) { // optimize !
x = cu.first.x/4 + cu.control.x/2 + cu.last.x/4;
y = cu.first.y/4 + cu.control.y/2 + cu.last.y/4;
}
Perspective geometry tells us that putting the points that describe a gxCurve or a gxPath through a gxMapping is accurate only if the gxMapping is affine; that is, it contains scaling, skewing, rotation and translation, but no perpsective. If a gxMapping is a perspective transformation, then a parabola becomes either a hyperbolic or elliptical segment. If any conic is sent through a perspective transformation, the result is another conic.
In Technote 1051 - Understanding Conic Splines ,, we learn that the parametric form for conics can be represented by sending the parametric equation for a quadratric B⁄zier through a perspective transformation:
Note that if we plug in 1.0 for con.lambda, the denominator becomes equal to 1.0; the numerator becomes identical to the CurveXY function derived above.
if (t == 0.5 && con.lambda == 1) { // further optimize !
x = con.a.x/4 + con.b.x/2 + con.c.x/4;
y = con.a.y/4 + con.b.y/2 + con.c.y/4;
}
which is identical to the equation for a gxCurve or parabola that we derived above.
In summary, what do we know?
n A second order parametric equation describes a parabolic segment.
n By adding a weighted divisor, conics can also be described by a parametric equation.
n If the weight in the conic equation is set to 1, the result is a parabolic segment.
Without any proof, itÕs worth knowing that if lambda is greater than 1, the conic equation describes a hyperbolic segment; if lambda is less than one, it describes an elliptical or circular segment.
Computing Lambda
Now letÕs determine the appropriate lambda va Älue for a circular arc. HereÕs the decidedy GX-centric approach weÕll take:
a) Construct a pair of lines perpendicular to the tangents at the arcÕs ends.
b) Define the circleÕs center to be the intersection of these lines.
c) Rotate one of these lines to the mid-angle to define the arcÕs mid-point.
d) Use the arcÕs mid-point to define the arcÕs lambda value.
So you can try this on your own,weÕll code this as legitimate fixed-point code.
#include <GraphicsLibraries.h>
#include <assert.h>
static void FindCircularLambda(conic& arc)
{
// we need a value for lambda that makes the midPoint equi-distant from the circle center.
// first, we need to find where the hypothetical center is. There are many ways to find
// the circle center;
// the way weÕll choose has a GX flavor; weÕll construct two radius lines and find where
// they intersect.
// start with the arc tangents from the end points to the control point
gxLine first = {{arc.a.x, arc.a.y}, {arc. 'b.x, arc.b.y}};
gxLine second = {{arc.c.x, arc.c.y}, {arc.b.x, arc.b.y}};
gxShape line1 = GXNewLine(&first);
gxShape line2 = GXNewLine(&second);
// these lines need to be rotated towards the circleÕs center.
// knowing the arc direction helps.
gxShape arcShape = GXNewCurve((gxCurve*) &arc);
Boolean direction = (GXGetShapeDirection(arcShape, 1) << 1) - 1;
// -1 counter, 1 clockwise
GXDisposeShape(arcShape);
// if the curve is clockwise, rotate the first 90¡ clockwise and
// the second 90¡ counter-clockwise
GXRotateShape(line1, direction * ff(90), arc.a.x, arc.a.y);
GX Libraries have a wealth of information and show how to use QuickDraw GX to solve real problems. The Conic Library shows how to use GX to construct paths that approximate conics, given three control points and a weight.
Reference Material
There are several different directions that conics can be taken. ItÕs possible that a future version of GX will directly support conics in all of its primitive operations. Until then, it is straight-forward to take the information presented here, forget all of it, and read Technote 1051 - Understanding Conic Splines instead to derive the code to transform conics through general gxMappings.
Another possible line of development is to adopt the general xy form equation for conics to use with GX. Foley and Van DammÕs venerable Computer Graphics (2nd edition) from Addison-Wesley presents code for scan c monverting conics in their general form. This algorithm is further explored on the Internet at http://www.ece.uiuc.edu/~ece291/class-resources/gpe/conic.cc.html.
There are also a number of Internet resources to explore conics further. Listing them here will likely produce references that quickly grow out of date, but you might try linking to http://www.geom.umn.edu/apps/conics/ or http://www.bham.ac.uk/mathwise/syl3_2.htm.
Further Reference
n Technote 1051 - Understanding Conic Splines
n MacOS SDK CD, Development Kits (Disc 2): QuickDraw GX: Programming Stuff: GX Libraries:
n Inside Macintosh: QuickDraw GX Objects
n Inside Macintosh: QuickDraw GX Environment and Utilities
Acknowledgments
Thanks to Tom Dowdy and Ingrid Kelly for reviewing this Technote.
Thanks to Michael Reed for the library, and Robert Johnson for still slogging it out after all of these years. Z ÿÿ N ° DSET ° ÿÿ . H ú]™] ÿÿÿÿÿÿı„0 ° √ A « Ø ° ÿÿ ˚ u J õ û ı„h \ 6 ÿÿ * A « bb • ± ÿ ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿ
••ÿÿ ˘•” • ± H H ı‰8 ÿ ÿÿÿÿÿÿ flflflflflfl ‡‡‡‡‡‡ üüüüüü ûûûûûû úúúúúú ùùùùùù øøøøøø ÷÷÷÷÷÷ öööööö
ÿÿÿÿ , % $ ÿÿ ) - . ÿÿÿÿ . - ÿÿ ÿÿÿÿ / + ÿÿ 'ÿÿÿÿ 0 ; ÿÿ + ÿÿÿÿ 1 E ÿÿ + ÿÿÿÿ 2 & ÿÿ , ÿÿÿÿ 3 5 ÿÿ (ÿÿÿÿ 4 C ÿÿ )ÿÿÿÿ 5 # ÿÿ 5 ÿÿÿÿ 6 : ÿÿ C ÿÿÿÿ 7 D ÿÿ ! ÿÿ 5 8 ? ÿÿ 5 ÿÿÿÿ 9 H ÿÿ 5 ÿÿÿÿ : 9 ÿÿ 5 ( ÿÿ : ; = ÿÿ 5 ( ÿÿÿÿ < > ÿÿ #ÿÿÿÿ = G ÿÿ > # ÿÿÿÿ > K ÿÿ > ÿÿÿÿ ? F ÿÿ *ÿÿÿÿ @ L ÿÿ F !ÿÿÿÿ A O ÿÿ F !ÿÿ , B 4 $ ÿÿÿÿ C @ ÿÿ ÿÿ ' D < ÿÿ ÿÿ - E A < ÿÿ + F 7 ÿÿ
ÿÿ B G N $ 7 ÿÿ C H P ÿÿ 7 ÿÿ < I S ÿÿ #ÿÿ > J Q ÿÿ S ÿÿÿÿ K R ÿÿ S , ÿÿ J L W ÿÿ S ÿÿ = M Y ÿÿ S # ÿÿÿÿ N V ÿÿ $ÿÿÿÿ O X ÿÿ % ÿÿ P Z X V & ÿÿ Q I ÿÿ ÿÿ R T ÿÿ ÿÿ S [ ÿÿ I ÿÿÿÿ T ^ ÿÿ I - ÿÿÿÿ U ` ÿÿ I . ÿÿÿÿ V " ÿÿ / ÿÿÿÿ W U ÿÿ , 3 ÿÿÿÿ X \ ÿÿ $ ÿÿ & Y a ÿÿ , ÿÿÿÿ Z _ ÿÿ , . ÿÿ Z [ b ÿÿ , . ÿÿ % \ c ÿÿ &ÿÿ Y ] d ÿÿ c ÿÿÿÿ ^ h ÿÿ > ÿÿ Q _ i ÿÿ ÿÿ ^ ` j ÿÿ i > ÿÿ S a k ÿÿ i ÿÿÿÿ b n ÿÿ , ÿÿ a c o ÿÿ ÿÿ c d p ÿÿ ÿÿ e ] ÿÿ ) ÿÿÿÿ f f ÿÿ , ? ÿÿÿÿ g ' ÿÿ
ÿÿ h / ÿÿ ÿÿ i 6 ÿÿÿÿ
ÿÿ j 8 ÿÿÿÿ
ÿÿ k e ÿÿÿÿ
ÿÿ % l g‹ ÿÿÿÿ ÿÿ m l0 g g ÿÿÿÿ n m0 g g ÿÿÿÿ o q0 g g ÿÿÿÿ p r0 g m ÿÿÿÿ q s0 g m ÿÿÿÿ r t0 g m ÿÿÿÿ s u0 g m
ÿÿÿÿ t v0 g m ÿÿÿÿ u w0 g m ÿÿÿÿ v x0 g l "
ÿÿÿÿ w y0 g l ' ÿÿÿÿ x z0 g q ) ÿÿÿÿ y {0 g q ÿÿÿÿ % z |‹ ÿÿÿÿ ÿÿ { }0 | | * ÿÿ n | ~0 | | ÿÿ o } 0 | | ÿÿÿÿ ~ •0 | ~ ) ÿÿ q ™0 | ~ ÿÿ r • ≠0 | ~ ÿÿ s ™ ∞0 | ~
# ÿÿÿÿ Ä Æ0 ¿ À B A ÿÿÿÿ Å Ç0 ¿ À B B ÿÿÿÿ Æ ÈØ ÿÿÿÿ
ÿÿ Ç É8 È È
ÿÿÿÿ È Ê8 È È
ÿÿÿÿ É Ë8 È È
ÿÿÿÿ Ê Ì8 È È
ÿÿÿÿ Ë Í8 È È
"ÿÿÿÿ Ì Î8 È È
%ÿÿÿÿ Í Ï8 È È
+ÿÿÿÿ Î ‹8 È È
,ÿÿÿÿ Ï Ñ8 È È
-ÿÿÿÿ ‹ Ò8 È È
.ÿÿÿÿ Ñ Ó8 È È
/ÿÿÿÿ Ò Ô8 È È
0ÿÿÿÿ Ó ÕØ ÿÿÿÿ C 1 ÿÿ Ô Ö8 Õ Õ D 2ÿÿÿÿ Õ ◊8 Õ Õ E 3ÿÿÿÿ Ö Ø8 Õ Õ F 4ÿÿÿÿ ◊ Ù8 Õ Õ G 5ÿÿÿÿ Ø Ú8 Õ Õ G 6ÿÿÿÿ Ù Û8 Õ Õ G 7ÿÿÿÿ Ú Ü8 Õ Õ G 8ÿÿÿÿ Û †8 Õ Õ G 9ÿÿÿÿ Ü fi8 Õ Õ G :ÿÿÿÿ † ß8 Õ Õ G ;ÿÿÿÿ fi àØ ÿÿÿÿ
< ÿÿ ß á8 à à
=ÿÿÿÿ à â8 à à
>ÿÿÿÿ á ã8 à à
?ÿÿÿÿ â ä8 à à
@ÿÿÿÿ ã å8 à à
Aÿÿÿÿ ä æ ' , H Bÿÿÿÿ å ç X , & Bÿÿ G æ è $ ÿÿ ≥ ≤ÿÿ HASH‘
Default SS Header Body Footer Footnote Footnote Index Heading1.H1 $ HeadingH2.H2 X HeadingH3.H3 'Code.CV /Italic 6Bullet 8 Checklist eNumber gClassic | Blue Gray 1 … Blue Gray 2 ˘Colorful œ
3D Table 1 ´
3D Table 2 ¿
Accounting ÈHarvard ÕLegal àDiamond d ÿÿ D FNTM Helvetica Geneva Palatino :H
